1. Field of the Invention
The present invention relates generally to communications networks, and more specifically to an on-demand QoS (quality-of-service)-based routing for a hierarchical communication network.
2. Description of the Related Art
RFC (Request for Comments) 2328 and 2676 texts describe a hierarchical communication network in which QoS-based on-demand routing is performed using the OSPF (Open Shortest Path First) algorithm, known as QOSPF (QoS extended OSPF). On-demand QoS routing algorithm is one that determines a QoS route to a user-specified destination using the Dijkstra algorithm. This QoS Touting is particularly useful for QoS-guaranteed networks such as multi-protocol label switching (MPLS) networks, The hierarchical communication network is comprised of a plurality of routers interconnected by links. Each of the routers belongs to one of a plurality of areas, one of which is the backbone area which is traversed by traffic between non-adjacent areas. Adjacent areas are interconnected by at least one router known as an area border router (ABR). If an area border router receives an on-demand QoS route calculation request from a user, requesting a route to a destination that is located in one of its neighboring areas, the router calculates a QoS-based shortest path tree (SPT) according to the Dijkstra algorithm. However, since the router has no knowledge of which areas can be traversed to reach the specified destination, the QoS-SPT calculation must be performed for all of its neighboring areas. Further, the router has no knowledge of which remote area border routers can be used as intermediate routers to reach a remote destination. Therefore, if the destination is in a remote area and can be reached via the backbone area, the QoS-SPT must be calculated for all possible routes of the backbone area from the source router to the remote area border routers, in addition to the QoS-SPT calculations for all possible routes of the local area of the source router. As a result, the prior art routing technique is wasteful of QoS-SPT calculations.